package a02_链表;

/**
 * <p>
 * a06_链表相交
 * </p>
 *
 * @author flyduck
 * @since 2024-06-19
 */
public class a07_链表相交复习2 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(8);
        listNode.next = new ListNode(4);
        listNode.next.next = new ListNode(5);

        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = listNode;

        ListNode headB = new ListNode(5);
        headB.next = new ListNode(0);
        headB.next.next = new ListNode(1);
        headB.next.next.next = listNode;

        ListNode intersectionNode = getIntersectionNode(headA, headB);
        System.out.println(intersectionNode.val);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1、求长度
        ListNode currentA = headA;
        int lengthA = 0;
        while (currentA != null) {
            currentA = currentA.next;
            lengthA++;
        }

        ListNode currentB = headB;
        int lengthB = 0;
        while (currentB != null) {
            currentB = currentB.next;
            lengthB++;
        }

        //2、长的先走
        currentA = headA;
        currentB = headB;
        if(lengthA > lengthB){
            int differLength = lengthA - lengthB;
            while (differLength > 0) {
                currentA = currentA.next;
                differLength--;
            }
        }else if(lengthB > lengthA){
            int differLength = lengthB - lengthA;
            while (differLength > 0) {
                currentB = currentB.next;
                differLength--;
            }
        }

        //3、同时走，如果相等就是相交
        while (currentA != null && currentB != null){
            if(currentA == currentB){
                return currentA;
            }else {
                currentA = currentA.next;
                currentB = currentB.next;
            }
        }
        return null;
    }
}
